#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <functional>
#include <cstdio>
#include <cassert>
#include <list>
#include <map>
#include <set>
#include <string>
#include <ctime>
#include <cstring>
using namespace std;

template <typename T>
class BinarySearchTree
{
	struct Node
	{
		Node(const T &val) : value(val), left(NULL), right(NULL) {}
		T value;
		Node *left, *right;
	};

public:
	BinarySearchTree()
	{
		root = NULL;
	}

	~BinarySearchTree()
	{
		clear();
	}

	bool contain(const T &val)
	{
		Node *p = root;
		while (p)
		{
			if (val < p->value)
				p = p->left;
			else if (val > p->value)
				p = p->right;
			else
				return true;
		}
		return false;
	}

	bool insert(const T &val)
	{
		return insertAt(root, val);
	}

	bool remove(const T &val)
	{
		return deleteNode(root, val);
	}

	void clear()
	{
		destroyTree(root);
		root = NULL;
	}

	void printSequence()
	{
		printNode(root);
	}

private:
	bool insertAt(Node *&nd, const T &val)
	{
		if (nd == NULL)
		{
			nd = new Node(val);
			return true;
		}

		if (val < nd->value)
			return insertAt(nd->left, val);
		else if (val > nd->value)
			return insertAt(nd->right, val);
		else
			return false;
	}

	bool deleteNode(Node *&nd, const T &val)
	{
		if (nd == NULL)
			return false;

		if (val < nd->value)
			return deleteNode(nd->left, val);
		else if (val > nd->value)
			return deleteNode(nd->right, val);
		else
		{
			deleteNode(nd);
			return true;
		}
	}

	void deleteNode(Node *&nd)
	{
		if (nd->right == NULL)
		{
			Node *tmp = nd;
			nd = nd->left;
			delete tmp;
			return;
		}

		if (nd->left == NULL)
		{
			Node *tmp = nd;
			nd = nd->right;
			delete tmp;
			return;
		}

		// set nd's value to be its rightest node's value of the left subtree
		// p is always p's parent node
		Node *p = nd;
		Node *q = nd->left;
		while (q->right)
		{
			p = q;
			q = q->right;
		}
		nd->value = q->value;

		if (p != nd)
			p->right = q->left;
		else
			p->left = q->left;

		delete q;
	}

	void destroyTree(Node *nd)
	{
		if (nd)
		{
			destroyTree(nd->left);
			destroyTree(nd->right);
			delete nd;
		}
	}

	void printNode(Node *nd)
	{
		if (nd)
		{
			printNode(nd->left);
			cout << nd->value << ' ';
			printNode(nd->right);
		}
	}


private:
	Node *root;
};

int main()
{
	BinarySearchTree<int> ba;

	srand(time(0));
	set<int> st;
	BinarySearchTree<int> bst;
	for (int i = 0; i < 200; i++)
	{
		int r = i;
		st.insert(r);
		bst.insert(r);
	}
	// random remove
	for (int i = 0; i < 100; i++)
	{
		int r = i;
		st.erase(r);
		bst.remove(r);
	}

	for (set<int>::iterator i = st.begin(); i != st.end(); i++)
		cout << *i << ' ';
	cout << endl;
	bst.printSequence();

	system("pause");
	return 0;
}